#include <iostream>
#define RED 0
#define BLACK 1
typedef int KEY_TYPE;

int key_compare(KEY_TYPE *a, KEY_TYPE *b) {

}

typedef struct _rbtree_node {
	unsigned char color;
	struct _rbtree_node* left;
	struct _rbtree_node* right;
	struct _rbtree_node* parent;//用于旋转
	KEY_TYPE key;
	void* value;

}rbtree_node;//红黑树节点

typedef struct _rbtree {
	rbtree_node* root;
	rbtree_node* nil;//通用的叶子结点
}rbtree;//红黑树

void _left_rotate(rbtree* T, rbtree_node* x) {//左旋
	//把x的右子树指向y的左子树
	rbtree_node* y = x->right;
	x->right = y->left;
	if (y->left != T->nil) {
		y->left->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == T->nil) {
		T->root = y;
	}
	else if (x == x->parent->left) {
		x->parent->left = y;
	}
	else {
		x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
}

void _right_rotate(rbtree* T, rbtree_node* y) {//右旋
	rbtree_node* x = y->left;
	y->left = x->right;
	if (x->right != T->nil) {
		x->right->parent = y;
	}
	x->parent = y->parent;
	if (y->parent == T->nil) {
		T->root = x;
	}
	else if (y == y->parent->right) {
		y->parent->right = x;
	}
	else {
		y->parent->left = x;
	}
	x->right = y;
	y->parent = x;
}

//调整插入节点
void rbtree_insert_fixup(rbtree* T, rbtree_node* z) {
	while (z->parent->color == RED) {
		if (z->parent == z->parent->parent->left) {
			rbtree_node* y = z->parent->parent->right;//叔父节点
			if (y->color == RED) {
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;//保证当前节点是红色的来循环
			}
			else {
				if (z == z->parent->right) {//将当前节点，当前节点的父亲节点和祖父节点调整到一个水平线上
					z = z->parent;
					_left_rotate(T, z);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				_right_rotate(T, z->parent->parent);
			}
		}
		else {
			rbtree_node* y = z->parent->parent->left;//叔父节点
			if (y->color == RED) {
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;//保证当前节点是红色的来循环
			}
			else {
				if (z == z->parent->left) {
					z = z->parent;
					_right_rotate(T, z);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				_left_rotate(T, z->parent->parent);
			}
		}
	}
	T->root->color = BLACK;//把根节点置为黑色
}

//插入节点
void rbtree_insert(rbtree* T, rbtree_node* z) {
	rbtree_node* x = T->root;
	rbtree_node* y = T->nil;
	while (x != T->nil) {
		y = x;//保证y是x的父节点
		if (z->key < x->key) {//比较可以换成自己定义的compared函数, 这样红黑树就可以做成模板
			x = x->left;
		}
		else if (z->key > x->key) {
			x = x->right;
		}
		else {
			return;//取决于应用场景,相同可以不插入，也可以修改后插入（加0.多），比如定时器时间一样，不能丢弃
		}
	}
	z->parent = y;
	if (y == T->nil) {
		T->root = z;
	}
	else if (z->key < y->key) {
		y->left = z;
	}
	else {
		y->right = z;
	}
	z->left = T->nil;
	z->right = T->nil;
	z->color = RED;
	rbtree_insert_fixup(T, z);
}